// 使用双端队列（Deque）来优化时间复杂度。
// 双端队列可以在队列的两端进行高效的插入和删除操作，


function maxSlidingWindow(nums, k) {
  // result 数组用于存储每个滑动窗口的最大值。
  // deque 双端队列用于存储元素的索引，队列中的索引对应的元素是单调递减的。
  const result = [];
  const deque = [];

  for (let i = 0; i < nums.length; i++) {
    // 移除队列中不在当前窗口内的元素
    // 第一个元素的索引小于 i - k，说明该元素已经不在当前窗口内
    if (deque.length > 0 && deque[0] <= i - k) {
      deque.shift();
    }

    // 移除队列中比当前元素小的元素
    // 从队列的末尾开始，移除所有比 nums[i] 小的元素的索引，因为这些元素不可能是后续窗口的最大值
    while (deque.length > 0 && nums[deque[deque.length - 1]] < nums[i]) {
      deque.pop();
    }

    // 将当前元素的索引加入队列
    deque.push(i);

    // 当窗口形成后，记录当前窗口的最大值
    // 当 i 大于等于 k - 1 时，说明窗口已经形成，队列的第一个元素的索引对应的元素就是当前窗口的最大值
    if (i >= k - 1) {
      result.push(nums[deque[0]]);
    }
  }

  return result;
}

